Many computer-implemented displays consist of two-dimensional arrays of individual picture elements, or pixels. To form an image, a rasterizer selectively illuminates these pixels. Because the individual pixels are so small, the display appears, to a human viewer, to be a continuous rendering of an image. This illusion is particularly effective for complex images of continuous tones such as photographs.
For simple geometric shapes, however, the pixelated nature of the display can become apparent to the human viewer. For example, if the rasterizer is instructed to draw a surface, there is no guarantee that the points on that surface will coincide with the pixels that are available for rendering it. As a result, a desired surface is often rendered as a set of pixels that are close to, but not necessarily coincident with, the desired surface. This results in surfaces that have a jagged or echeloned appearance.
A surface is typically formed by combining a large number of small surface elements. Thus, in the course of rendering a surface, a large number of polygonal surface elements are drawn. Because of the ease with which it can be assembled to form surfaces having complex curves, a particularly suitable polygonal surface element is a triangular surface element.
To render a surface element, the rasterizer must frequently select those pixels that will minimize the jagged appearance of the resulting surface element. A straightforward mathematical approach is to use the equations of the lines defining the edges of the surface element and to derive the equation of a plane containing those lines. The rasterizer can then choose pixels whose coordinates minimize a least-square error across all points on the line. While such an approach has the advantage of globally optimizing the selection of pixels on the surface element, the large number of floating-point operations required causes this approach to be prohibitively time-consuming.
To meet constraints on speed, rasterizers typically implement rasterization methods that avoid time-consuming floating-point operations. However, known rasterization methods rely on the assumption that the array of pixels is arranged in a uniform rectangular grid that can readily be modeled by a Cartesian coordinate system. This was a reasonable assumption given the prevalence of two-dimensional displays such as computer monitors and printers at the time such algorithms were developed.
Since then, however, volumetric, or three-dimensional displays have been developed. Such displays permit the generation, absorption, or scattering of visible radiation from a set of localized and specified regions within a volume. Examples of such systems are taught in Hirsch U.S. Pat. No. 2,967,905, Ketchpel U.S. Pat. No. 3,260,424, Tsao U.S. Pat. No. 5,754,267, and on pages 66-67 of Aviation Week, Oct. 31, 1960.
In such displays, the more natural coordinate system is a cylindrical coordinate system. Because of the unusual properties of the cylindrical coordinate system, rasterization methods for Cartesian coordinate systems cannot readily be applied to rasterize surfaces in a cylindrical coordinate system.